FIG. 1 is a block diagram of conventional network 100. Conventional network 100 includes nodes 110, 120, and 130 which are interconnected by communication channels 140, 150, and 160. Nodes 110, 120, and 130 may be layer 2 switches, Layer 2/Layer 3 switches, bridges or the like. Communication channels 140, 150, and 160 may be unshielded twisted pair wire, coaxial cable, shielded twisted pair wire, fiber-optic cable, wireless connections, or other media suitable for interconnecting nodes.
Network 100 may use a layered architecture. A layered architecture is a hardware or software design in which the functions of one layer build upon the functions of a lower layer. Typically, each layer uses the services provided by the layer immediately below it and provides services to the layer above it. The well-known Open Systems Interconnection (OSI) reference model developed by the International Standardization Organization (ISO) is one exemplary model for layered architecture. Layer 2 of the OSI model is responsible for creating, transmitting, and receiving digitally encoded packets. From the perspective of layer 2, nodes may be identified by their Media Access Control (MAC) addresses.
Forwarding is the process of passing a packet or message on to an intermediate or final destination. Forwarding may be performed by layer 2 hardware and software modules of network 100 (layer 2 forwarding). The fundamental properties of layer 2 forwarding are flooding, learning, and aging.
Nodes typically make forwarding decisions based on a forwarding table. A forwarding table typically provides a listing of addresses with associated interfaces through which the address may be reached. When a packet is received on an interface of a node, the node reads the source address (typically a MAC address) and updates the forwarding table with an entry indicating that the source address may be reached through the interface on which the packet was received. Learning refers to the process of building a forwarding table based on information obtained from received packets. Typically a node will discard forwarding table entries that have not been updated after a predetermined period. Aging refers to monitoring the age of forwarding table entries and discarding stale entries.
The receiving node may also access the destination address of the received packet and compare that address to the forwarding table. Typically, the destination address will be one of three types: unicast, multicast, or broadcast. If the destination address is a unicast address and the node has an entry in its forwarding table that corresponds to that unicast address, then the node will forward the packet through the interface indicated by the entry in the forwarding table. If there is no entry corresponding to the unicast address then the node may forward the packet over all interfaces except the interface on which the packet was received. Flooding refers to the process of forwarding a packet over all interfaces except an interface on which a packet was received. Packets having a multicast or broadcast destination address may also be flooded.
Referring again to FIG. 1, network 100 illustrates that the process of flooding may create a network loop if more than one path exists between any two nodes in network 100. For example, node 110 may send packet 170, having an unknown unicast address to node 120. Node 120 determines that packet 170 has an unknown unicast address and sends it over all available interfaces (e.g., over communication channel 150). Node 130 similarly determines that packet 170 has an unknown unicast address and forwards the packet to node 110. Thus, a network loop occurs when a network provides alternate paths between nodes so that a flooded packet returns to the node from which it was sent.
A redundancy protocol is a protocol that provides a mechanism to control and/or prevent network loops. Examples of redundancy protocols include the IEEE 802.1D standard, 1998 Edition (ISO/IEC 15802-3:1998); the IEEE 802.1w-2001 standard, 2001 Edition; RFC 2338, “Virtual Router Redundancy Protocol,” S. Knight, et al, April 1998 (VRRP); and the Extreme Standby Redundancy Protocol (ESRP). Redundancy protocols are well known by those of ordinary skill in the art. For ease of discussion, nodes are herein described as having redundancy protocols rather than having implementations of redundancy protocols.
FIG. 2 is a block diagram of network 200, illustrating how a redundancy protocol may limit the occurrence of a network loop. Network 200 includes nodes and communication channels similar to those in network 100 and those nodes and communication channels are similarly numbered. Reference numerals 215, 225, and 235 are instances of a redundancy protocol operating on nodes 210, 220, and 230 respectively. Redundancy protocols 215, 225, and 235 may communicate with each other by exchanging control packets. As is well known in the art, redundancy protocols 215, 225, and 235 may render one or more interfaces on nodes 210, 220, and 230 inactive to reduce the occurrence of network loops.
In the illustrated example of FIG. 2, interface 270 on node 220 is inactive. Since the interface on node 220 is inactive there is only one active path between any two nodes in network 200. The redundancy protocols operating on nodes 210, 220, and 230 reduce the occurrence of network loops by attempting to ensure that there is only one active path between a source node and a destination node in network 200.
A problem may occur, however, if there is a software failure or another anomaly in communication between the redundancy protocols operating on nodes 210, 220, and 230. For example, processing resources on node 210 may be too busy to generate and process the control packets that direct node 220 to maintain interface 260 in an inactive state. After a predetermined period of time, node 220 may bring interface 260 to an active state. Once interface 260 is in an active state, there will be more than one active path between each node in network 200. Therefore, network 200 will likely experience network loops.